// Package day_14_two_point 1-167
// @Title day_14_two_point
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/7 16:16
// @Create  2021/9/7 16:16
package day_14_two_point

// 双指针做法  O(N) O(1)
func twoSum(numbers []int, target int) []int {
	if numbers == nil {
		return nil
	}
	l, r := 0, len(numbers)-1
	for l < r {
		if numbers[l]+numbers[r] == target {
			return []int{l + 1, r + 1}
		} else if numbers[l]+numbers[r] > target {
			r--
		} else {
			l++
		}
	}
	return []int{}
}

// 二分法查找  因为数组是严格升序 O(n*LogN) - O(1)
func TwoSumFast(numbers []int, target int) []int {
	left, right := 0, len(numbers)-1
	for left <= right {
		mid := left + (right-left)>>1
		if numbers[left]+numbers[right] == target && left != right {
			return []int{left + 1, right + 1}
		} else if numbers[left]+numbers[mid] < target {
			left = mid
		} else {
			right = mid
		}
	}
	return []int{}
}
